/**
    ******************************************************************************
    * @file    AVLTree.c
    * @author  debian
    * @version V1.0.0
    * @date    2019-12-20
    * @brief   平衡二叉树
    ******************************************************************************
    * @attention
    *
    *
    ******************************************************************************
    */ 

/* Includes ------------------------------------------------------------------*/
#include "AVLTree.h"
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <assert.h>


/** @addtogroup DataStruct_Driver
    * @{
    */

/** @addtogroup AVLTree
    * @{
    */

/* Private typedef -----------------------------------------------------------*/

/* Private define ------------------------------------------------------------*/

/* Private macro -------------------------------------------------------------*/

/* Private variables ---------------------------------------------------------*/

/* Private function prototypes -----------------------------------------------*/

/* Private functions ---------------------------------------------------------*/


/** @defgroup AVLTree_Exported_Functions AVLTree Exported Functions
    * @{
    */

/** @defgroup AVLTree_Exported_Functions_Group1 Initialization and deinitialization functions
    *  @brief    Initialization and Configuration functions
    *
@verbatim    
    ===============================================================================
                ##### Initialization and deinitialization functions #####
    ===============================================================================
    [..]
        This section provides functions allowing to initialize and de-initialize the AVLTree
        to be ready for use.
 
@endverbatim
    * @{
    */ 


    
/**
    * @}
    */

/** @defgroup AVLTree_Exported_Functions_Group2 operation functions 
    *  @brief   operation functions
    *
@verbatim   
    ===============================================================================
                        ##### operation functions #####
    ===============================================================================
    [..]
        This subsection provides a set of functions allowing to manage the AVLTree.

@endverbatim
    * @{
    */

	/**
		* @brief  AVL树左旋
		* @param  
		* @retval 
		*/ 
		static int AVLTree_L_Rotate(struct AVLTree_node **node)
		{
			//node为这颗最小不平衡树的根结点（node结点就是他的父结点的左右指针的一个）
			struct AVLTree_node *root = *node;

			//获取根结点的右子树 R
			struct AVLTree_node *R_node = root->bst.right;

			//把Rl挂接到根结点的右子树上
			root->bst.right = R_node->bst.left;
			
			//根结点成为R的左子树
			R_node->bst.left = root;

			//R替换根结点
			*node = R_node;    //把父结点的孩子指针指向了R结点

			return 0;
		}
		

	/**
		* @brief  AVL树右旋
		* @param  
		* @retval 
		*/ 
		static int AVLTree_R_Rotate(struct AVLTree_node **node)
		{
			//node为这颗最小不平衡树的根结点（node结点就是他的父结点的左右指针的一个）
			struct AVLTree_node *root = *node;

			//获取根结点的左子树 L
			struct AVLTree_node *L_node = root->bst.left;

			//把Lr挂接到根结点的左子树上
			root->bst.left = L_node->bst.right;

			//根结点成为L的右子树
			L_node->bst.right = root;
			
			//L替换根结点
			*node = L_node;    //把父结点的孩子指针指向了L结点

			return 0;
		}


#define 	LH 		+1	/* 左子树高 */
#define 	EH 		0	/* 等高 */
#define 	RH 		-1	/* 右子树高 */


	/**
		* @brief  AVL左平衡 (BF<0的时候的情况)
		* @param  
		* @retval 算法处理完之后，node指针已经被修改了值 
		*/ 
		int AVLTree_LeftBalance(struct AVLTree_node **node)
		{
			//node为这颗最小不平衡树的根结点（node结点就是他的父结点的左右指针的一个）
			struct AVLTree_node *root = *node;

			//获取根结点的左子树 L
			struct AVLTree_node *L_node = root->bst.left;
			struct AVLTree_node *Lr_node = L_node->bst.right;

			//根结点的BF<0的时候,   它的左子树的bf   有两种情况：
			printf("AVLTree_LeftBalance %d\n", L_node->bst.bf);
			switch(L_node->bst.bf)
			{
				//新插入的元素是插在root的左子树上的时候，只需要右旋就好
				case LH:
					//右旋也是分两种情况，但是这两种情况的结果是一样的，根结点的bf值和L_node结点的bf值都为0
					root->bst.bf = L_node->bst.bf = EH;		
					AVLTree_R_Rotate(node);
					break;

				//如果是反向的话，就需要双旋了，双旋比较复杂有三种情况的
				case RH:
					switch(Lr_node->bst.bf)
					{
						case EH:
							//想等的情况最简单，记得这是处理完，双旋之后的结果，双旋之后的结果就是两个bf=0
							root->bst.bf = L_node->bst.bf = 0;
							break;

						//下面这两种情况，在上面的图解上已经分析过了，平衡二叉树的难点就是BF值的更新，真难
						case LH: 
							root->bst.bf = RH;
							L_node->bst.bf = EH;
							break;

						case RH:
							root->bst.bf = EH;
							L_node->bst.bf = LH;
							break;
					}

					Lr_node->bst.bf = 0;

					AVLTree_L_Rotate(&root->bst.left);
					AVLTree_R_Rotate(node);
					break;
			}

			return 0;
		}


	/**
		* @brief  AVL右平衡 (BF<0的时候的情况)
		* @param  
		* @retval 算法处理完之后，node指针已经被修改了值 
		*/ 
		int AVLTree_RightBalance(struct AVLTree_node **node)
		{
			//node为这颗最小不平衡树的根结点（node结点就是他的父结点的左右指针的一个）
			struct AVLTree_node *root = *node;

			//获取根结点的左子树 L
			struct AVLTree_node *R_node = root->bst.right;
			struct AVLTree_node *Rl_node = R_node->bst.left;

			//根结点的BF<0的时候,   它的右子树的bf   有两种情况：
			printf("AVLTree_RightBalance %d\n", R_node->bst.bf);
			switch(R_node->bst.bf)
			{
				//新插入的元素是插在root的右子树上的时候，只需要左旋就好
				case RH:
					//左旋也是分两种情况，但是这两种情况的结果是一样的，根结点的bf值和L_node结点的bf值都为0
					root->bst.bf = R_node->bst.bf = EH;		
					AVLTree_L_Rotate(node);
					break;

				//如果是反向的话，就需要双旋了，双旋比较复杂有三种情况的
				case LH:
					printf("AVLTree_RightBalance LH %d\n", Rl_node->bst.bf);
					switch(Rl_node->bst.bf)
					{
						case EH:
							//想等的情况最简单，记得这是处理完，双旋之后的结果，双旋之后的结果就是两个bf=0
							root->bst.bf = Rl_node->bst.bf = 0;
							break;

						//下面这两种情况，在上面的图解上已经分析过了，平衡二叉树的难点就是BF值的更新，真难
						case LH: 
							root->bst.bf = EH;
							R_node->bst.bf = RH;
							break;

						case RH:
							root->bst.bf = LH;
							R_node->bst.bf = EH;
							break;
					}

					Rl_node->bst.bf = 0;

					AVLTree_R_Rotate(&root->bst.right);
					AVLTree_L_Rotate(node);
					break;
			}

			return 0;
		}


	/**
		* @brief  AVL创建一个新结点
		* @param  
		* @retval 
		*/ 
		static struct AVLTree_node* AVLTree_creat_node(Elemtype data, int bf)
		{
			//申请一个结点
			struct AVLTree_node *node = (struct AVLTree_node *)malloc(sizeof(struct AVLTree_node));
			assert(node);

			//填充数据
			node->data = data;
			node->bst.bf = bf;
			node->bst.left = NULL;
			node->bst.right = NULL;

			return node;
		}	

	
	/**
		* @brief  AVL删除一个结点,删除结点有几种情况，跟二叉树的差不多
		* @param  
		* @retval 
		*/ 
		static struct AVLTree_node* AVLTree_delect_node(struct AVLTree_node **node, int *flag)
		{
			struct AVLTree_node *q, *s;

			//只有右子树，需要接父结点的右子树
			if((*node)->bst.left == NULL)  {			
				*node = (*node)->bst.right;
				free(*node);
				*flag = 1;
			}else if((*node)->bst.right == NULL)  {   //只有左子树,只接左子树
				*node = (*node)->bst.left;
				free(*node);
				*flag = 1;
			}else {		
				//左右子树都存在，直接寻找要删除结点的直接前继
				//直接前继就是node结点的左子树的最后边的数据
				s = (*node)->bst.left;
				q = (*node);
				while(s->bst.right)
				{
					q = s;s = s->bst.right;		//寻找最右边的结点，还要考虑这个结点是否有左子树
				}
				printf("s = %d\n", s->data);
				//q要保存，这是s的父结点，s的左子树要挂在到q这个结点上
				if(q == (*node))  //相等的话，就是s=node左子树，已经是直接后继了
				{
					//不改变
					printf("q == node\n");

					switch((*node)->bst.bf)			//根据这个结点之前的数据来修改值
					{
						case EH:
							s->bst.bf = RH;
							*flag = 0;
							break;
						case RH:
							s->bst.bf = EH;
							AVLTree_RightBalance(&s);
							*flag = 1;
							break;
						case LH:
							s->bst.bf = EH;
							*flag = 0;
							break;
					}
				}
				else		//不想等的话，说明node的左子树是有右子树的，q是s的父节点，s是q的右子树，s的左子树要挂在q的右子树上
				{		
					q->bst.right = s->bst.left;
					s->bst.left = (*node)->bst.left;
				}

				
				

				
				s->bst.right = (*node)->bst.right;
				free(*node);
				*node = s;
				printf("noe = %p\n", *node);

				//调整结点的BF


				
				
			}
			
			return 0;
		}	


	/**
		* @brief  AVL插入操作（用递归比较好）
		* @param  flag = 0 不需要调整    ，flag=1  需要调整 
		* @retval 
		*/ 
		static int AVLTree_Insert(struct AVLTree_node **node, Elemtype data, int *flag)
		{
			if(!(*node)) 			//递归调用，如果这个结点为空，说明插入的结点就是这个位置
			{
				*node = AVLTree_creat_node(data, EH);		//申请一个新的结点，并退出递归
				*flag = 1;
				printf("creat node %p %d\n", *node, data);
				
			}
			else    				//如果这个结点存在，需要查找到插入的位置
			{
				if( data < (*node)->data )			//如果插入的data数据比结点的data小，需要从左子树寻找位置  
				{
					AVLTree_Insert(&((*node)->bst.left),  data, flag);		//这个需要左子树寻找位置，记得这里是递归

					//假如这里递归完成,需要调整bf值，有一下情况：
					
					printf("lflag = %d %d\n", *flag, (*node)->bst.bf);

					if(*flag)
					{
						//递归调整平衡二叉树的bf，很巧妙
						switch((*node)->bst.bf)  //这个已经插入完成，开始回调修改bf值了
						{
							case EH:   //看图2，位置1
								(*node)->bst.bf = LH;
								*flag = 1;
								break;

							case LH:	//本来已经是左高了，现在插入左子树，左子树就超过了,需要左平衡处理，6.1.6会详细说明这种情况
								AVLTree_LeftBalance(node);
								*flag = 0;
								break;

							case RH:	//看图1  ，位置3
								(*node)->bst.bf = EH;
								*flag = 0;
								break;
						}
					}
				}
				else 
				{
					AVLTree_Insert(&((*node)->bst.right),  data, flag);     //这时候是往右子树插入

					//递归调整平衡二叉树的bf，很巧妙
					printf("Rflag = %d %d\n", *flag, (*node)->bst.bf);
					if(*flag)
					{
						switch((*node)->bst.bf)  //这个已经插入完成，开始回调修改bf值了
						{
							case EH:   
								//右边跟左边是反方向的，这个相等的就不画了，根图2差不多，需要递归回去修改祖父结点的bf值
								(*node)->bst.bf = RH;
								*flag = 1;
								break;

							case LH:	
								//如果是左子树高，插入右子树就等高了,跟图1差不多，这个只需要修改父节点的bf值即可，不需要修改祖父结点的
								(*node)->bst.bf = EH;
								*flag = 0;
								break;

							case RH:	//本来已经是右高了，现在又插入右子树，右子树就超过了,需要右平衡处理，6.1.7会详细说明这种情况
								AVLTree_RightBalance(node);
								*flag = 0;
								break;
						}
					}
				}
			}
			
			return 0;
		}


	/**
		* @brief  AVL删除操作（用递归比较好）
		* @param  flag = 0 不需要调整    ，flag=1  需要调整 
		* @retval 
		*/ 
		static int AVLTree_delete(struct AVLTree_node **node, Elemtype data, int *flag)
		{
			if(!(*node)) 						//如果没有找到返回错误
			{
				*flag = 0;
				return -1;
			}
		
			if((*node)->data == data) 			//判断结点是不是需要删除的节点，如果是调用删除函数
			{
				*node = AVLTree_delect_node(node, flag);			//删除一个结点
				printf("AVLTree_delete\n");
				//*flag = 1;
			}
			else    				//如果没有找到
			{
				if( data < (*node)->data )			//如果要删除的data数据比结点的data小，需要从左子树寻找位置  
				{
					AVLTree_delete(&((*node)->bst.left),  data, flag);		//这个需要左子树寻找位置，记得这里是递归

					//假如这里递归完成,需要调整bf值，有一下情况：  这些需要修改
					
					printf("lflag = %d %d %d\n", *flag, (*node)->bst.bf, (*node)->data);

					if(*flag)
					{
						//递归调整平衡二叉树的bf，很巧妙
						switch((*node)->bst.bf)  //这个已经插入完成，开始回调修改bf值了
						{
							case EH:   //如果之前是想等的，删除了左孩子的话，就变成RH
								(*node)->bst.bf = RH;
								*flag = 0;
								break;

							case LH:	//本来已经是左高了，现在删除左孩子，父节点就平衡了，但是需要调整祖父结点
								(*node)->bst.bf = EH;
								*flag = 1;
								break;

							case RH:	//本来就右边高，现在又删除左孩子，右边就不平衡了，需要调节
								AVLTree_RightBalance(node);
								*flag = 0;
								break;
						}
					}
				}
				else 
				{
					AVLTree_delete(&((*node)->bst.right),  data, flag);     //这时候是往右子树插入

					printf("Rflag = %d %d %d\n", *flag, (*node)->bst.bf, (*node)->data);

					//递归调整平衡二叉树的bf，很巧妙，需要修改
					if(*flag)
					{
						switch((*node)->bst.bf)  //这个已经插入完成，开始回调修改bf值了
						{
							case EH:   
								//如果之前是想等的，删除了右孩子的话，就变成LH
								(*node)->bst.bf = LH;
								*flag = 0;
								break;

							case LH:	
								//本来就左边高，现在又删除右孩子，右边就不平衡了，需要调节
								AVLTree_LeftBalance(node);;
								*flag = 0;
								break;

							case RH:	//本来已经是右高了，现在删除右孩子，父节点就平衡了，但是需要调整祖父结点
								(*node)->bst.bf = EH;
								*flag = 1;
								break;
						}
					}
				}
			}
			
			return 0;
		}



		
	#if 1
		/**
			* @brief  前序遍历,先遍历根结点，再左子树，然后右子树
			* @param	
			* @retval 
			*/ 
			static  void bstree_preOrderTraversal(struct AVLTree_node* node)
			{	
				if(node == NULL)
					return ;

				printf("%d %d ", node->data, node->bst.bf);
				bstree_preOrderTraversal(node->bst.left);
				bstree_preOrderTraversal(node->bst.right);	
			}


		int main()
		{
			int i = 0;
			int ret = -1;
			int aa[] = {12, 45, 89, 127, 7, 4, 56, 60, 9, 14,16, 58};
			int flag = 0;
	
			struct AVLTree T = {0};		//二叉树头结点
			

			//二叉树是左结点比双亲结点小，右结点比双亲结点大
			for(i=0; i<12; i++)
			{
				printf("根结点  b %p\n", T.root);
				AVLTree_Insert(&(T.root), aa[i], &flag);
				printf("根结点 h  %p\n", T.root);
				bstree_preOrderTraversal(T.root);
				printf("\n");
			}
			
			//前序遍历二叉树
			bstree_preOrderTraversal(T.root);
			printf("\n");

			//biTree_search(T.root, 124);
			printf("删除结点 h  %p\n", T.root);
			AVLTree_delete(&(T.root), 60, &flag);
			bstree_preOrderTraversal(T.root);
			printf("\n");
			AVLTree_delete(&(T.root), 56, &flag);
			AVLTree_delete(&(T.root), 16, &flag);
			bstree_preOrderTraversal(T.root);
			printf("\n");
			
			AVLTree_delete(&(T.root), 89, &flag);
			//AVLTree_delete(&(T.root), 58, &flag);
			//AVLTree_delete(&(T.root), 127, &flag);
			
			//biTree_insert(&T, 567);
			bstree_preOrderTraversal(T.root);
			printf("\n");
			
			return 0;
	
		}
	#endif



    /**
    * @}
    */


/**
    * @}
    */

/**
    * @}
    */

/**
    * @}
    */

/************************ (C) 2019 HOME 深圳龙华 *****END OF FILE****/

